package demo1;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //最长公共子序列
    public int longestCommonSubsequence(String text1, String text2) {
        int row = text1.length();
        int column = text2.length();
        int [][] dp = new int [row+1][column+1];
        for(int i = 1;i<=row;i++){
            for(int j = 1;j<=column;j++){
                if(text1.charAt(i-1)==text2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[row][column];
    }

    //有序数组中的单一元素
    public int singleNonDuplicate(int[] nums) {
        int n = nums.length;
        int left = 0;
        int right = n-1;
        if(left==right || nums[left]!=nums[left+1]) return nums[left];
        if(nums[right]!=nums[right-1]) return nums[right];
        while (left < right) {
            int mid = left + (right-left)/2;
            if(nums[mid] == nums[mid+1]){
                if((mid-left)%2==1) right = mid-1;
                else left = mid;
            }else if(nums[mid] == nums[mid-1]){
                if((mid-left)%2==1) left = mid+1;
                else right = mid;
            }else return nums[mid];
        }
        return nums[right];
    }
}
